package com.cjm.algorithm.leetcode;

import com.cjm.algorithm.TreeNode;

import java.util.*;

public class SmallestFromLeaf988 {
    private static Map<Integer, String> map = new HashMap<>(26);
    static {
        map.put(0, "a");
        map.put(1, "b");
        map.put(2, "c");
        map.put(3, "d");
        map.put(4, "e");
        map.put(5, "f");
        map.put(6, "g");
        map.put(7, "h");
        map.put(8, "i");
        map.put(9, "j");
        map.put(10, "k");
        map.put(11, "l");
        map.put(12, "m");
        map.put(13, "n");
        map.put(14, "o");
        map.put(15, "p");
        map.put(16, "q");
        map.put(17, "r");
        map.put(18, "s");
        map.put(19, "t");
        map.put(20, "u");
        map.put(21, "v");
        map.put(22, "w");
        map.put(23, "x");
        map.put(24, "y");
        map.put(25, "z");
    }
    public String smallestFromLeaf(TreeNode root) {
        TreeSet<String> res = new TreeSet<String>();
        dfs(root, res, "");
        return res.first();
    }

    private void dfs(TreeNode root, TreeSet<String> res, String item) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            res.add(map.get(root.val) + item);
            return;
        }
        item = map.get(root.val) + item;
        dfs(root.left, res, item);
        dfs(root.right, res, item);
    }
}
